package leetcode.editor.cn;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.stream.Collectors;

/**
 * 题目Id：LCR 015
 * 题目：找到字符串中所有字母异位词
 * 日期：2023-12-14 13:25:14
 */
//给定两个字符串 s 和 p，找到 s 中所有 p 的 变位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。 
//
// 变位词 指字母相同，但排列不同的字符串。 
//
// 
//
// 示例 1： 
//
// 
//输入: s = "cbaebabacd", p = "abc"
//输出: [0,6]
//解释:
//起始索引等于 0 的子串是 "cba", 它是 "abc" 的变位词。
//起始索引等于 6 的子串是 "bac", 它是 "abc" 的变位词。
// 
//
// 示例 2： 
//
// 
//输入: s = "abab", p = "ab"
//输出: [0,1,2]
//解释:
//起始索引等于 0 的子串是 "ab", 它是 "ab" 的变位词。
//起始索引等于 1 的子串是 "ba", 它是 "ab" 的变位词。
//起始索引等于 2 的子串是 "ab", 它是 "ab" 的变位词。
// 
//
// 
//
// 提示: 
//
// 
// 1 <= s.length, p.length <= 3 * 10⁴ 
// s 和 p 仅包含小写字母 
// 
//
// 
//
// 注意：本题与主站 438 题相同： https://leetcode-cn.com/problems/find-all-anagrams-in-a-
//string/ 
//
// Related Topics 哈希表 字符串 滑动窗口 👍 62 👎 0


public class VabMRr {
    public static void main(String[] args) {
        Solution solution = new VabMRr().new Solution();
        List<Integer> anagrams = solution.findAnagrams("cbaebabacd", "abc");
        System.out.println(anagrams);

        System.out.println("Hello world");
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        /**
         * 暴力法每次都重新比较滑动窗口内的所有字符，优化成只计算滑动的字符
         * 1，统计字符串p的字符频率
         * 2，统计窗口i=0的字符串s的前p.lenght频率，并判断和1是否相等
         * 3，滑动窗口，遍历i
         * 4，删除s字符串位置i的字符，添加i+p.lenght的字符频率
         * 5，判断
         * @param s
         * @param p
         * @return
         */
        public List<Integer> findAnagrams(String s, String p) {
            List<Integer> list = new ArrayList<>();
            if(s==null||s.length()<p.length()){
                return list;
            }
            int[] pCount=new int[26];
            int[] sCount=new int[26];
            for (int i = 0; i < p.length(); i++) {
                pCount[p.charAt(i)-'a']++;
                sCount[s.charAt(i)-'a']++;
            }
            if(Arrays.equals(pCount,sCount)){
                list.add(0);
            }
            for (int i=0;i<s.length()-p.length();i++){
                sCount[s.charAt(i)-'a']--;
                sCount[s.charAt(i+p.length())-'a']++;

                if(Arrays.equals(pCount,sCount)){
                    list.add(i+1);
                }
            }
            return list;

        }


    }




//leetcode submit region end(Prohibit modification and deletion)
}

